/**
 * 390. 消除游戏
 * https://leetcode-cn.com/problems/elimination-game/
 */
public class Solutions_390 {
    public static void main(String[] args) {
        for (int i = 1; i <= 10; i++) {
            int result = lastRemaining(i);
            System.out.println(i + " => " + result);
        }
    }

    /**
     * 解题思路:找规律
     */
    public static int lastRemaining(int n) {
        int diff = 1;
        int first = 1;
        boolean fromLeft = true;
        int count = n;
        while (count > 1) {
            if (fromLeft) {
                // 从左往右移除元素时,首位需要删除
                first += diff;
            } else {
                if (count % 2 == 0) {
                    // 从右往左移除元素时，若变化后的数列为偶数长度，首位不变

                } else {
                    // 从右往左移除元素时，若变化后的数列为奇数长度，首位需要删除
                    first += diff;
                }
            }
            fromLeft = !fromLeft;
            // 公差翻倍
            diff *= 2;
            // 变化一次后，数列长度减半
            count /= 2;
        }
        return first;
    }
}
